#include <stdio.h>
#include <stdlib.h>
#define MAX(a, b)  ( (a) > (b) ? (a) : (b) )

typedef struct AVLNode 
{
	int data;
	AVLNode* right;
	AVLNode* left;
	int height;
};

int Height(AVLNode* node)
{
	if (nullptr == node)
	{
		return -1;
	}
	else
	{
		return node->height;
	}
}

AVLNode* LLRotation(AVLNode* parent)
{
	AVLNode* root = parent->left;
	parent->left = root->right;
	root->right = parent;

	parent->height = MAX(Height(parent->left), Height(parent->right)) + 1;
	root->height = MAX(Height(root->left), Height(root->right)) + 1;

	return root;
}

AVLNode* RRRotation(AVLNode* parent)
{
	AVLNode* root = parent->right;
	parent->right = root->left;
	root->left = parent;

	parent->height = MAX(Height(parent->left), Height(parent->right)) + 1;
	root->height = MAX(Height(root->left), Height(root->right)) + 1;

	return root;
}

AVLNode* LRRotation(AVLNode* parent)
{
	parent->left = RRRotation(parent->left);

	return LLRotation(parent);
}

AVLNode* RLRotation(AVLNode* parent)
{
	parent->right = LLRotation(parent->left);

	return RRRotation(parent);
}

AVLNode* addAVLNode(AVLNode* parent, AVLNode* node)
{
	if (nullptr == parent)
	{
		return node;
	}
	else if (node->data < parent->data)
	{
		parent->left = addAVLNode(parent->left, node);
		if (Height(parent->left) - Height(parent->right) == 2)
		{
			if (node->data < parent->left->data)
				parent = LLRotation(parent);
			else
				parent = LRRotation(parent);
		}
	}
	else if (node->data > parent->data)
	{
		parent->right = addAVLNode(parent->right, node);
		if (Height(parent->right) - Height(parent->left) == 2)
		{
			if (node->data > parent->right->data)
				parent = RRRotation(parent);
			else
				parent = RLRotation(parent);
		}
	}

	parent->height = MAX(Height(parent->left), Height(parent->right))+1;
	return parent;
}

int main()
{
	AVLNode* roots = (struct AVLNode*)malloc(sizeof(struct AVLNode));
	roots->left = 0;
	roots->right = 0;
	roots->height = 0;

	srand(2200);
	for (int i = 1; i < 7; i++)
	{
		int curr = i;
		//int curr = rand();
		//printf("Curr: %d\n", curr);
		if (i == 1)
		{
			roots->data = curr;
		}
		else
		{
			AVLNode* avln = (struct AVLNode*)malloc(sizeof(struct AVLNode));
			avln->data = curr;
			avln->left = NULL;
			avln->right = NULL;
			avln->height = 0;
			roots = addAVLNode(roots, avln);
		}
	}
	printf("Done.\n");
	return 0;
}